package _17_剑指Offer;

public class _14_剑指OfferI剪绳子 {

    public static void main(String[] args) {

        _14_剑指OfferI剪绳子 v = new _14_剑指OfferI剪绳子();

        System.out.println(v.cuttingRope(3));

    }

    public int cuttingRope(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        return res * n;
    }

    public int cuttingRope1(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // 拆分绳子
            for (int j = i - 1; j > 0; j--) {
                int sub = i - j;
                dp[i] = Math.max(Math.max(sub * dp[j], dp[i]), sub * j);
            }
        }
        return dp[n];
    }
}
